home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1997 / MacHack 1997.toast / Hacks / Hacks ’97 / Warrior’s Progress / source code / Source / Libraries / BitArray / Bits.cp < prev    next >
Encoding:
Text File  |  1997-06-28  |  4.9 KB  |  170 lines  |  [TEXT/CWIE]
  1. // Bits.cp
  2.  
  3. #ifndef Bits_h
  4. #include "Bits.h"
  5. #endif
  6.  
  7. uint32 Bits::Count( uint16 n )
  8.   {
  9.     return count[ Byte0(n) ]
  10.           + count[ Byte1(n) ];
  11.   }
  12.         
  13. uint32 Bits::Count( uint32 n )
  14.   {
  15.     return count[ Byte0(n) ]
  16.           + count[ Byte1(n) ]
  17.           + count[ Byte2(n) ]
  18.           + count[ Byte3(n) ];
  19.   }
  20.  
  21. uint32 Bits::FirstZero( uint16 n )
  22.   {
  23.     if ( Byte0( n ) != 0xff )
  24.         return FirstZero( Byte0( n ) );
  25.     
  26.     return FirstZero( Byte1(n) ) + 8;
  27.  }
  28.         
  29. uint32 Bits::FirstZero( uint32 n )
  30.   {
  31.     if ( Byte0( n ) != 0xff )
  32.         return FirstZero( Byte0( n ) );
  33.     
  34.     if ( Byte1( n ) != 0xff )
  35.         return FirstZero( Byte1(n) ) + 8;
  36.     
  37.     if ( Byte2( n ) != 0xff )
  38.         return FirstZero( Byte2(n) ) + 16;
  39.     
  40.     return FirstZero( Byte3(n) ) + 24;
  41.   }
  42.  
  43. uint32 Bits::LastZero( uint16 n )
  44.   {
  45.     if ( Byte1( n ) != 0xff )
  46.         return LastZero( Byte1( n ) ) + 8;
  47.     
  48.     return LastZero( Byte0(n) );
  49.   }
  50.         
  51. uint32 Bits::LastZero( uint32 n )
  52.   {
  53.     if ( Byte3( n ) != 0xff )
  54.         return LastZero( Byte3( n ) ) + 24;
  55.     
  56.     if ( Byte2( n ) != 0xff )
  57.         return LastZero( Byte2(n) ) + 16;
  58.     
  59.     if ( Byte1( n ) != 0xff )
  60.         return LastZero( Byte1(n) ) + 8;
  61.     
  62.     return LastZero( Byte0(n) );
  63.   }
  64.  
  65. uint16 Bits::Reverse( uint16 n )
  66.   {
  67.     return uint16( Reverse( Byte0( n ) ) ) << 8
  68.           | uint16( Reverse( Byte1( n ) ) );
  69.   }
  70.         
  71. uint32 Bits::Reverse( uint32 n )
  72.   {
  73.     return uint32( Reverse( Byte0( n ) ) ) << 24
  74.           | uint32( Reverse( Byte1( n ) ) ) << 16
  75.           | uint32( Reverse( Byte2( n ) ) ) << 8
  76.           | uint32( Reverse( Byte3( n ) ) );
  77.   }
  78.  
  79. const uint8 Bits::count[ maxuint8 + 1 ] =
  80.   {
  81.     0,1,1,2,  1,2,2,3,  1,2,2,3,  2,3,3,4,
  82.     1,2,2,3,  2,3,3,4,  2,3,3,4,  3,4,4,5,
  83.     1,2,2,3,  2,3,3,4,  2,3,3,4,  3,4,4,5,
  84.     2,3,3,4,  3,4,4,5,  3,4,4,5,  4,5,5,6,
  85.     
  86.     1,2,2,3,  2,3,3,4,  2,3,3,4,  3,4,4,5,
  87.     2,3,3,4,  3,4,4,5,  3,4,4,5,  4,5,5,6,
  88.     2,3,3,4,  3,4,4,5,  3,4,4,5,  4,5,5,6,
  89.     3,4,4,5,  4,5,5,6,  4,5,5,6,  5,6,6,7,
  90.     
  91.     1,2,2,3,  2,3,3,4,  2,3,3,4,  3,4,4,5,
  92.     2,3,3,4,  3,4,4,5,  3,4,4,5,  4,5,5,6,
  93.     2,3,3,4,  3,4,4,5,  3,4,4,5,  4,5,5,6,
  94.     3,4,4,5,  4,5,5,6,  4,5,5,6,  5,6,6,7,
  95.     
  96.     2,3,3,4,  3,4,4,5,  3,4,4,5,  4,5,5,6,
  97.     3,4,4,5,  4,5,5,6,  4,5,5,6,  5,6,6,7,
  98.     3,4,4,5,  4,5,5,6,  4,5,5,6,  5,6,6,7,
  99.     4,5,5,6,  5,6,6,7,  5,6,6,7,  6,7,7,8
  100.   };
  101.  
  102. const uint8 Bits::firstZero[ maxuint8 + 1 ] =
  103.   {
  104.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,4,
  105.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,5,
  106.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,4,
  107.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,6,
  108.     
  109.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,4,
  110.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,5,
  111.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,4,
  112.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,7,
  113.  
  114.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,4,
  115.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,5,
  116.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,4,
  117.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,6,
  118.     
  119.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,4,
  120.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,5,
  121.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,4,
  122.     0,1,0,2,  0,1,0,3,  0,1,0,2,  0,1,0,8
  123.   };
  124.  
  125. const uint8 Bits::lastZero[ maxuint8 + 1 ] =
  126.   {
  127.     7,7,7,7,  7,7,7,7,  7,7,7,7,  7,7,7,7,
  128.     7,7,7,7,  7,7,7,7,  7,7,7,7,  7,7,7,7,
  129.     7,7,7,7,  7,7,7,7,  7,7,7,7,  7,7,7,7,
  130.     7,7,7,7,  7,7,7,7,  7,7,7,7,  7,7,7,7,
  131.  
  132.     7,7,7,7,  7,7,7,7,  7,7,7,7,  7,7,7,7,
  133.     7,7,7,7,  7,7,7,7,  7,7,7,7,  7,7,7,7,
  134.     7,7,7,7,  7,7,7,7,  7,7,7,7,  7,7,7,7,
  135.     7,7,7,7,  7,7,7,7,  7,7,7,7,  7,7,7,7,
  136.  
  137.     6,6,6,6,  6,6,6,6,  6,6,6,6,  6,6,6,6,    
  138.     6,6,6,6,  6,6,6,6,  6,6,6,6,  6,6,6,6,    
  139.     6,6,6,6,  6,6,6,6,  6,6,6,6,  6,6,6,6,    
  140.     6,6,6,6,  6,6,6,6,  6,6,6,6,  6,6,6,6,    
  141.  
  142.     5,5,5,5,  5,5,5,5,  5,5,5,5,  5,5,5,5,
  143.     5,5,5,5,  5,5,5,5,  5,5,5,5,  5,5,5,5,
  144.     4,4,4,4,  4,4,4,4,  4,4,4,4,  4,4,4,4,
  145.     3,3,3,3,  3,3,3,3,  2,2,2,2,  1,1,0,8
  146.   };
  147.  
  148. const uint8 Bits::reverse[ maxuint8 + 1 ] =
  149.   {
  150.     0x00,0x80,0x40,0xc0,  0x20,0xa0,0x60,0xe0,  0x10,0x90,0x50,0xd0,  0x30,0xb0,0x70,0xf0,
  151.     0x08,0x88,0x48,0xc8,  0x28,0xa8,0x68,0xe8,  0x18,0x98,0x58,0xd8,  0x38,0xb8,0x78,0xf8,
  152.     0x04,0x84,0x44,0xc4,  0x24,0xa4,0x64,0xe4,  0x14,0x94,0x54,0xd4,  0x34,0xb4,0x74,0xf4,
  153.     0x0c,0x8c,0x4c,0xcc,  0x2c,0xac,0x6c,0xec,  0x1c,0x9c,0x5c,0xdc,  0x3c,0xbc,0x7c,0xfc,
  154.  
  155.     0x02,0x82,0x42,0xc2,  0x22,0xa2,0x62,0xe2,  0x12,0x92,0x52,0xd2,  0x32,0xb2,0x72,0xf2,
  156.     0x0a,0x8a,0x4a,0xca,  0x2a,0xaa,0x6a,0xea,  0x1a,0x9a,0x5a,0xda,  0x3a,0xba,0x7a,0xfa,
  157.     0x06,0x86,0x46,0xc6,  0x26,0xa6,0x66,0xe6,  0x16,0x96,0x56,0xd6,  0x36,0xb6,0x76,0xf6,
  158.     0x0e,0x8e,0x4e,0xce,  0x2e,0xae,0x6e,0xee,  0x1e,0x9e,0x5e,0xde,  0x3e,0xbe,0x7e,0xfe,
  159.  
  160.     0x01,0x81,0x41,0xc1,  0x21,0xa1,0x61,0xe1,  0x11,0x91,0x51,0xd1,  0x31,0xb1,0x71,0xf1,
  161.     0x09,0x89,0x49,0xc9,  0x29,0xa9,0x69,0xe9,  0x19,0x99,0x59,0xd9,  0x39,0xb9,0x79,0xf9,
  162.     0x05,0x85,0x45,0xc5,  0x25,0xa5,0x65,0xe5,  0x15,0x95,0x55,0xd5,  0x35,0xb5,0x75,0xf5,
  163.     0x0d,0x8d,0x4d,0xcd,  0x2d,0xad,0x6d,0xed,  0x1d,0x9d,0x5d,0xdd,  0x3d,0xbd,0x7d,0xfd,
  164.  
  165.     0x03,0x83,0x43,0xc3,  0x23,0xa3,0x63,0xe3,  0x13,0x93,0x53,0xd3,  0x33,0xb3,0x73,0xf3,
  166.     0x0b,0x8b,0x4b,0xcb,  0x2b,0xab,0x6b,0xeb,  0x1b,0x9b,0x5b,0xdb,  0x3b,0xbb,0x7b,0xfb,
  167.     0x07,0x87,0x47,0xc7,  0x27,0xa7,0x67,0xe7,  0x17,0x97,0x57,0xd7,  0x37,0xb7,0x77,0xf7,
  168.     0x0f,0x8f,0x4f,0xcf,  0x2f,0xaf,0x6f,0xef,  0x1f,0x9f,0x5f,0xdf,  0x3f,0xbf,0x7f,0xff
  169.   };
  170.